package 中等.贪心思想;

/**
 * 给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
 * 斐波那契数字定义为：
 * F1 = 1
 * F2 = 1
 * Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
 * 数据保证对于给定的 k ，一定能找到可行解。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
 */
public class 和为K的最少斐波那契数字数目_1414 {

    public static void main(String[] args) {

        System.out.println(new 和为K的最少斐波那契数字数目_1414().findMinFibonacciNumbers(7));

    }

    private int[] fibonacci = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597,
            2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811,
            514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817,
            39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733};

    /**
     * 贪心+二分+打表
     * 想要得到和为 k 的最小数量，那么需要尽可能选择较大的数字，使得相加的
     * 数量要少一些
     *
     * @param k
     * @return
     */
    public int findMinFibonacciNumbers(int k) {
        int curK = k, count = 0;
        while (curK > 0) {
            // 因为斐波那契数列中存在 1 ，且可以重复选择多次，所以一定存在解
            // 优先选择的斐波那契数列中 <= k 的最大索引一定是答案中的一个数字
            curK -= fibonacci[search(curK)];
            count++;
            if (curK == 0) return count;
        }
        return count;
    }

    // 二分找到小于目标值的最大索引
    private int search(int target) {
        int ans = 0;
        int left = 0, right = fibonacci.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (fibonacci[mid] <= target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

}
